package com.example.tree.heap;

import com.example.linked.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。(和 leetcode378 类似)
 *  请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *  示例 1：
 *  输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 *
 *  示例 2：
 *  输入：lists = []
 * 输出：[]
 */
public class Leetcode23_MergeKLists {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode list3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = {list1, list2, list3};
        for (ListNode list : lists) {
            ListNode cur = list;
            while (cur != null) {
                System.out.print(cur.val + " -> ");
                cur = cur.next;
            }
            System.out.println();
        }

        ListNode mergedList = new Solution().mergeKLists(lists);

        ListNode cur = mergedList;

        while (cur != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }


    }

    static class Solution {
        /**
         * 归并排序的归的过程
         * 一般归并排序是两个数组(链表)归并，而本题是 n 个数组(链表)归并，所以需要用小根堆维护，以优化找到最小值的时间复杂度。
         *
         * @param lists
         * @return
         */
        public ListNode mergeKLists(ListNode[] lists) {
//            Queue<ListNode> minHeap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
            Queue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val)); // 等价上面的写法

            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null)
                    minHeap.offer(lists[i]);
            }

            ListNode mergedHead = new ListNode(-1);
            ListNode cur = mergedHead;
            while (!minHeap.isEmpty()) {
                ListNode tmp = minHeap.poll();
                cur.next = tmp;
                cur = cur.next;
                if (tmp.next != null) // 当前链表未合并完毕,需要将当前链表的下一个节点加入到最小堆中去,因为它可能是下一个要合并的节点
                    minHeap.offer(tmp.next);
            }

            return mergedHead.next;
        }
    }
}
